Various cipher algorithms are utilized as fundamental technologies of security systems. Generally, cipher algorithms are classified into two groups, namely, public key cryptosystems and common key cryptosystems. The public key cryptosystems use different keys for encryption and decryption. The public key cryptosystems keep a key for decrypting ciphertext called a secret key as secret information only for a receiver, instead of making a key for encryption called a public key publicly available, to thereby ensure high security. The common key cryptosystems, on the other hand, use the same key for encryption and decryption called a common key. The common key cryptosystems keep a common key as information unknown to any third party other than the sender and receiver to thereby ensure high security.
The cipher algorithms of the common key cryptosystems have the advantages of high processing speed and compact packaging over the cipher algorithms of the public key cryptosystems. Therefore, the encryption function is added to compact devices such as mobile phones or integrated-circuit (IC) cards using the cipher algorithms of the common key cryptosystems. Furthermore, due to the high processing speed and real-time encryption/decryption of information, the cipher algorithms of the common key cryptosystems are also used for broadcasting or information communication in communication fields.
The cipher algorithms of the common key cryptosystems are classified into two types, namely, stream ciphers and block ciphers. Now, the block ciphers are widely used in terms of security. The block ciphers divide plaintext into blocks each having a certain bit length, and encrypt the plaintext block by block. The bit length of each block which is the unit of encryption is called “block length”.
There are many block ciphers of the common key cryptosystems with various types of block sizes such as 64-bit, 128-bit and others. Typical cipher algorithms include DES (Data Encryption Standard), AES (Advanced Encryption Standard), SC2000, MISTY1, MISTY2, KASUMI, and CAMELLIA. Such cipher algorithms of the common key cryptosystems are implemented by software or hardware.
One of the cipher algorithms of the common key cryptosystems, MISTY1, will now be described. MISTY1 is described in, for example, Specification of MISTY1 (<http://www.cryptrec.go.jp/cryptrec—03_spec_cypherlist_files/PDF/05—02jspec.pdf>). MISTY1 is a cipher algorithm with a common key size of 128 bits and a block length of 64 bits. That is, MISTY1 generates 64-bit ciphertext from 64-bit plaintext using a 128-bit common key. In the following, a description will be given of a round processing part of MISTY1.
FIGS. 10A and 10B are circuit diagrams illustrating an example configuration of a MISTY1 round processing part. FIG. 10A illustrates a round processing part for use in the decryption process. FIG. 10B illustrates a round processing part for use in the encryption process.
The round processing part of MISTY1 illustrated in FIGS. 10A and 10B performs processing where the number of rounds n is 8. In Specification of MISTY1 mentioned above, 8 rounds are recommended. The round processing part of MISTY1 has a Feistel structure with eight FO functions FO1, FO2, FO3, FO4, FO5, FO6, FO7, and FO8 and ten FL functions FL1, FL2, FL3, FL4, FL5, FL6, FL7, FL8, FL9, and FL10 or ten FL−1 functions FL1−1, FL2−1, FL3−1, FL4−1, FL5−1, FL6−1, FL7−1, FL8−1, FL9−1, and FL10−1. In the encryption process of MISTY1, 64-bit plaintext P is input and 64-bit ciphertext C is output. In the decryption process, 64-bit ciphertext C is input and 64-bit plaintext P is output.
In the following, a description will be given of the FL functions and the FL−1 functions.
FIG. 11A is a circuit diagram illustrating an example configuration of an FL function. FIG. 11B is a circuit diagram illustrating an example configuration of an FL−1 function. The FL function includes an AND gate 1a in the first stage and an OR gate 2a in the second stage. Conversely to the FL function, the FL−1 function includes an OR gate 2b in the first stage and an AND gate 1b in the second stage.
32-bit input data to the FL function and the FL−1 function is divided into two data segments of 16 bits each, and each data segment is transformed using an XOR gate, an AND gate, and an OR gate. In FIGS. 11A and 11B, KLij (1≦i≦8, 1≦j≦2) represents 16-bit data at the j-th position from the left of KLi, where KLi denotes an extended key. In MISTY1, extended-key processing is performed to generate a 256-bit extended key KLi from a 128-bit secret key K. The details of the generation of an extended key are described in Specification of MISTY1 mentioned above.
In the FL function, the bit string of the upper 16 bits of the 32-bit input and the upper 16 bits KLi1 of the extended key are input to the AND gate 1a. The bit string of the lower 16 bits of the 32-bit input and the output of the AND gate 1a are input to an XOR gate 3a. The output of the XOR gate 3a and the lower 16 bits KLi2 of the extended key are input to the OR gate 2a. The bit string of the upper 16 bits of the 32-bit input and the output of the OR gate 2a are input to an XOR gate 3b. The output of the XOR gate 3b corresponds to the upper 16 bits of a 32-bit output of the FL function, and the output of the XOR gate 3a corresponds to the lower 16 bits of the 32-bit output of the FL function.
In the FL−1 function, the bit string of the lower 16 bits of the 32-bit input and the lower 16 bits KLi2 of the extended key are input to the OR gate 2b. The bit string of the upper 16 bits of the 32-bit input and the output of the OR gate 2b are input to an XOR gate 3c. The output of the XOR gate 3c and the upper 16 bits KLi1 of the extended key are input to the AND gate 1b. The bit string of the lower 16 bits of the 32-bit input and the output of the AND gate 1b are input to an XOR gate 3d. The output of the XOR gate 3c corresponds to the upper 16 bits of a 32-bit output of the FL−1 function, and the output of the XOR gate 3d corresponds to the lower 16 bits of the 32-bit output of the FL−1 function.
A method for implementing an FL function and an FL−1 function in a first typical example will now be described.
In a hardware implementation supporting both the encryption process and the decryption process, it is necessary to implement an FL function and an FL−1 function. FIG. 12 is a circuit diagram illustrating an implementation method in the first typical example. In the first typical example, an FL function 6 and an FL−1 function 7 can be switched using a selector 5 depending on the encryption process or the decryption process.
A method for implementing an FL function and an FL−1 function in a second typical example will now be described.
A compact implementation method for implementing an FL function and an FL−1 function has been available. Such an implementation method is described in, for example, Japanese Patent No. 4128395. FIG. 13 is a circuit diagram illustrating an implementation method in the second typical example. In the second typical example, a single AND gate 1c and a single OR gate 2c are used for implementation. In the second typical example, therefore, an AND gate and an OR gate, which are common parts between the two functions, are shared and the functions are merged into a single function.
In FIG. 13, the bit string of the lower 16 bits of a 32-bit input and the output of the AND gate 1c are input to an XOR gate 3e. The bit string of the upper 16 bits of the 32-bit input and the output of the OR gate 2c are input to an XOR gate 3f. The bit string of the upper 16 bits of the 32-bit input and the output of the XOR gate 3f are input to a selector 5a. The bit string of the lower 16 bits of the 32-bit input and the output of the XOR gate 3e are input to a selector 5b. The output of the selector 5a and the upper 16 bits KLi1 of an extended key are input to the AND gate 1c. The output of the selector 5b and the lower 16 bits KLi2 of the extended key are input to the OR gate 2c. The output of the XOR gate 3f corresponds to the upper 16 bits of a 32-bit output of the circuit illustrated in FIG. 13, and the output of the XOR gate 3e corresponds to the lower 16 bits of the 32-bit output of the circuit illustrated in FIG. 13.
When each of the selectors 5a and 5b selects the upper signal, the circuit illustrated in FIG. 13 serves as an FL function. When the lower signals are selected, the circuit serves as an FL−1 function. This technique allows a significant reduction in circuit size. A related technique is disclosed in Dai Yamamoto, et al., “A Very Compact Hardware Implementation of the MISTY1 Block Cipher”, CHES 2008, LNCS 5154, pp. 315-330, 2008, or Akashi Satoh and Sumio Morioka, “Small and High-Speed Hardware Architectures for the 3GPP Standard Cipher KASUMI”, Information Security Conference 2002, LNCS 2433, pp. 48-62, 2002.